package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 54. 螺旋矩阵
 * @date 2025/3/17 10:42
 */
public class E54 {

    /**
     * <h3>while循环模拟</h3>
     *
     * @param matrix 矩阵
     * @return 遍历的结果
     */
    public List<Integer> spiralOrder1(int[][] matrix) {
        // 1. i、j记录当前位置，m、n记录矩阵的行数和列数，result记录遍历的结果
        int i = 0, j = 0, m = matrix.length, n = matrix[0].length;
        List<Integer> result = new ArrayList<>();
        // 2. visited记录当前位置是否被访问过，如果被访问过，则跳过该位置
        boolean[][] visited = new boolean[m][n];
        // 3. 先将第一个位置加入结果集，并标记为已访问
        result.add(matrix[0][0]);
        visited[0][0] = true;
        // 4. 用于退出条件，如果指针没动了，说明遍历完了
        boolean moved = false;
        // 5. 模拟遍历，每次循环都遍历完一圈，直到遍历完所有元素
        while (true) {
            // 5.1 向右走到底
            while (j < n - 1 && !visited[i][j + 1]) {
                result.add(matrix[i][j + 1]);
                visited[i][j + 1] = true;
                j++;
                moved = true;
            }
            // 5.2 向下走到底
            while (i < m - 1 && !visited[i + 1][j]) {
                result.add(matrix[i + 1][j]);
                visited[i + 1][j] = true;
                i++;
                moved = true;
            }
            // 5.3 向左走到底
            while (j > 0 && !visited[i][j - 1]) {
                result.add(matrix[i][j - 1]);
                visited[i][j - 1] = true;
                j--;
                moved = true;
            }
            // 5.4 向上走到底
            while (i > 0 && !visited[i - 1][j]) {
                result.add(matrix[i - 1][j]);
                visited[i - 1][j] = true;
                i--;
                moved = true;
            }
            // 5.5 如果没有移动过，说明遍历完了，退出循环
            if (!moved) break;
            moved = false;
        }
        // 6. 返回结果
        return result;
    }

    /**
     * <h3>方法二：使用方向数组</h3>
     * @param matrix 矩阵
     * @return 遍历的结果
     */
    public List<Integer> spiralOrder2(int[][] matrix){
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0, n = matrix.length, m = matrix[0].length, round = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[n][m];
        for(int num = 1; num <= n * m; num++){
            result.add(matrix[i][j]);
            visited[i][j] = true;
            i += directions[round][0];
            j += directions[round][1];
            if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j]){
                i -= directions[round][0];
                j -= directions[round][1];
                round = (round + 1) & 3;
                i += directions[round][0];
                j += directions[round][1];
            }
        }
        return result;
    }
}
